The present invention relates to routing protocols in computer networks, and more particularly, routing protocols in ad hoc networks with radio links.
Multi-hop packet-radio networks, or ad hoc networks, consist of mobile hosts interconnected by routers that can also move. The deployment of such routers is ad hoc and the topology of such networks is very dynamic, because of host and router mobility, signal loss and interference, and power outages. In addition, the channel bandwidth available in ad hoc networks is relatively limited compared to wired networks, and untethered routers may need to operate with battery-life constraints. In these networks, routing must preferably be accomplished using as few a number of control messages and neighbor-to-neighbor handshakes as possible, in order to conserve channel bandwidth for user data and preserve the battery life of untethered nodes. Because of the dynamics of the topology in an ad hoc network, broadcast radio links are preferable for interconnecting routers without the need for topology planning.
Routing protocols for computer networks can be categorized according to: (a) the type of information the protocols use to compute preferred paths, and (b) the way in which routers obtain routing information. In terms of the type of information used by routing protocols, routing protocols can be classified into link-state protocols and distance-vector protocols. Routers running a link-state protocol use topology information to make routing decisions; routers running a distance-vector protocol use distances and, in some cases, path information, to destinations to make routing decisions.
In terms of the way in which routers obtain information, routing protocols have been classified as either table-driven or on-demand. In an on-demand routing protocol, routers maintain path information for only those destinations that they need to contact as a source or relay of information. The basic approach consists of allowing a router that does not know how to reach a destination to send a flood-search message to obtain the path information it needs. One of the first routing protocols of this type was proposed to establish virtual circuits in the MSE network, see V. O. K. Li and R. Chang, xe2x80x9cProposed routing algorithms for the US Army mobile subscriber equipment (MSE) network,xe2x80x9d Proc. IEEE MILCOM""86, Monterey, Calif., October 1986, and there are several other, recent examples of this approach (e.g., AODV, see C. Perkins, xe2x80x9cAd Hoc On Demand Distance Vector (AODV) Routing,xe2x80x9d draft-ietf-manet-aodv-00.txt, November 1997; ABR, see C-K. Toh, xe2x80x9cWireless ATM and Ad Hoc Networks,xe2x80x9d Kluwer, November 1996; DSR, see D. Johnson and D. Maltz, xe2x80x9cProtocols for Adaptive Wireless and Mobile Networking,xe2x80x9d IEEE Pers. Commun., Vol. 3, No. 1, February 1996; TORA, see V. Park and M. Corson, xe2x80x9cA Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,xe2x80x9dxe2x80x2 Proc. IEEE INFOCOM 97, Kobe, Japan, April 1997; SSA, see R. Dube et al., xe2x80x9cSignal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks,xe2x80x9d IEEE Pers. Commun., February 1997; and ZRP, see Z. Haas and M. Pearlman, xe2x80x9cThe Zone Routing Protocol for Highly Reconfigurable Ad Hoc Networks,xe2x80x9d Proc. ACM SIGCOMM 98, Vancouver, British Columbia, August 1998). The Dynamic Source Routing (DSR) protocol has been shown to outperform many other on-demand routing protocols. J. Broch et al, xe2x80x9cA Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,xe2x80x9d Proc. ACM MOBICOM 98, Dallas, Tex., October 1998. The existing on-demand routing protocols differ on the specific mechanisms used to disseminate flood-search packets and the responses thereto, the means used to cache information received during other nodes"" searches, and the manner in which to determine the cost of a link and the existence of a neighbor. However, one common characteristic of all of the on-demand routing protocols reported to date is that such protocols are based on distances to destinations. Stated differently, there have been no on-demand link-state routing protocol proposals to date.
In a table-driven scheme, each router maintains path information for each known destination in the network and updates its routing-table entries as needed. Examples of table-driven algorithms based on distance vectors are the routing protocol of the DARPA packet-radio network, J. Jubin and J. Tomow, xe2x80x9cThe DARPA Packet Radio Network Protocols,xe2x80x9d Proceedings of the IEEE, Vol. 75, No. 1, January 1987; DSDV, C. Perkins and P. Bhagwat, xe2x80x9cHighly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,xe2x80x9d Proc. ACM SIGCOMM 94, London, UK, October 1994; WRP, S. Murthy and J. J. Garcia-Luna-Aceves, xe2x80x9cAn Efficient Routing Protocol for Wireless Networks,xe2x80x9d ACM Mobile Networks and Applications Journal, Special issue on Routing in Mobile Communication Networks, 1996; WIRP, J. J. Garcia-Luna-Aceves et al., xe2x80x9cWireless Internet Gateways (WINGS),xe2x80x9d Proc. IEEE MILCOM""97, Monterey, Calif., November 1997; and least-resistance routing protocols, M Pursley and H. B. Russell, xe2x80x9cRouting in Frequency-Hop Packet Radio Networks with Partial-Band Jamming,xe2x80x9d IEEE Trans. Commun., Vol. 41, No. 7, pp. 1117-1124, 1993.
Prior table-driven approaches to link-state routing in packet-radio networks are based on topology broadcasts. However, disseminating complete link-state information to all routers incurs excessive communication overhead in an ad hoc network because of the dynamics of the network and the small bandwidth available. Accordingly, all existing link-state routing approaches for packet-radio networks have been based on hierarchical routing schemes. R. Ramanathan and M. Steenstrup, xe2x80x9cHierarchically-organized, Multihop Mobile Wireless Networks for Quality-of-Service Support,xe2x80x9d ACM Mobile Networks and Applications, Vol.3, No. 1, pp. 101-119, 1998; C. V. Ramamoorthy and W. Tsai, xe2x80x9cAn Adaptive Hierarchical Routing Algorithm,xe2x80x9d Proceedings of IEEE COMPSAC ""83, Chicago, Ill., pp. 93-104, November 1983; and M. Steenstrup (ed.), Routing in Communication Networks, Prentice-Hall, 1995. Also, prior proposals for link-state routing using partial link-state data without clusters, see, e.g., J. J. Garcia-Luna-Aceves and J. Behrens, xe2x80x9cDistributed, scalable routing based on vectors of link states,xe2x80x9d IEEE Journal on Selected Areas in Communications, Vol. 13, No. 8, 1995; and J. J. Garcia-Luna-Aceves and M. Spohn, xe2x80x9cScalable Link-State Internet Routing,xe2x80x9d Proc. IEEE International Conference on Network Protocols (ICNP 98), Austin, Tex., Oct. 14-16, 1998, require routers to explicitly inform their neighbors which links they use and which links they stop using.
A number of prior routing protocols are based on the notion of routing trees, in which routers communicate either the state (i.e., cost or length) of the links in a shortest-path routing tree, or the distance from the root of the tree and the second-to-last hop in the routing tree for each node in the tree. An early example of this type of protocol was proposed in U.S. Pat. No. 4,466,060 to Riddle. In Riddle""s protocol, a router communicates different routing trees to different neighbors; such trees are called xe2x80x9cexclusionary treesxe2x80x9d and specify the preferred paths to destinations excluding those paths that involve the router to which the update is being sent. An update packet or message specifies an entire exclusionary tree. Another protocol based on routing trees was reported by Garcia-Luna-Aceves, J. J. Garcia-Luna-Aceves, xe2x80x9cA Fail-Safe Routing Algorithm for Multihop Packet-Radio networks,xe2x80x9d Proc. IEEE Infocom 86, Miami, Fla., April 1986, which protocol differs from Riddle""s protocol in that the same routing tree is sent incrementally by a router to all its neighbors. A. Humblet, xe2x80x9cAnother Adaptive Shortest-Path Algorithm,xe2x80x9d IEEE Trans. Comm., Vol.39, No.6, June 1991, pp.995-1003 (and see U.S. Pat. No. 4,987,536); Cheng et al., C. Cheng et al., xe2x80x9cA Loop-Free Extended Bellman-Ford Routing Protocol without Bouncing Effectxe2x80x9d, Proc. ACM SIGCOMM 89, pp.224-236; B. Rajagopalan and M. Faiman, xe2x80x9cA Responsive Distributed Shortest-Path Routing Algorithm within Autonomous Systems,xe2x80x9d Journal of Internetworking: Research and Experience}, Vol. 2, No. 1, March 1991, pp. 51-69; and S. Murthy and J. J. Garcia-Luna-Aceves, xe2x80x9cLoop-Free Internet Routing Using Hierarchical Routing Trees,xe2x80x9d Proc. IEEE INFOCOM 97, Kobe, Japan, Apr. 7-11, 1997, have all proposed protocols based on source trees in which a router communicates to its neighbors the same shortest-path routing tree incrementally and these latter examples differ from the above-cited protocol by Garcia-Luna-Aceves in the way in which a router obtains its own source tree from the trees reported by its neighbors. An important feature of all prior routing tree-based protocols is the fact that they are all based on communicating routing trees in terms of the lengths of the links and the identifiers of the nodes that form part of the routing trees.
In one embodiment of the present scheme, one or more labeled routing trees (LRTs) are produced at a router of a computer network according to a shortest path determination made over a partial topology graph of the network, which graph is produced according to knowledge of adjacent links of the router and one or more LRTs of neighboring routers. The LRTs of the router may be updated in response to receipt of routing state update messages, and such messages may include local link identifiers assigned by a head of a link to which the identifiers pertain, and node parameters of a tail of the link to which the local link identifiers pertain. The routing state update messages may be transmitted within the network: (i) in response to a new destination node being detected by an existing node within the network, (ii) in response to a destination becoming unreachable by a collection of the existing nodes, (iii) in response to the change in the cost of a path to at least one destination exceeding a threshold delta, and/or (iv) in situations where a routing loop may be encountered among two or more of the nodes of the network (e.g., at times when a path implied in the LRT of the router leads to a loop).
In another embodiment, the present routing protocol allows for distributing local link identifiers among nodes of a computer network within routing state update messages. These local link identifiers are preferably assigned by a head of a link to which the identifiers pertain. The routing state update messages may include state parameters for nodes at tails of links to which the identifiers pertain. The routing protocol may further provide for distributing labeled routing trees of the nodes of the computer network among the nodes, for example wherein each node of the computers network may distribute its labeled routing trees to its neighboring nodes.
In such a routing protocol each node of the computer network preferably maintains one labeled routing tree per type of service offered in the network. These labeled routing trees may be generated according to a partial topology graph derived from the node""s adjacent links and labeled routing trees of neighboring nodes, for example by applying a path selection algorithm to the partial topology graph. The labeled routing trees may then be updated in response to receipt of the routing state update messages. Such updates may be made according to either an optimum routing approach or a least overhead routing approach, depending upon which approach is used within the computer network.
For the optimum routing approach, routing state update messages are preferably transmitted: (i) when a routing state update message which causes a link to be added to a subject node""s labeled routing trees is received, (ii) when a more recent routing state update message regarding an existing link in the subject node""s labeled routing trees is received, and/or (iii) when a destination becomes unreachable by the subject node. In the least overhead routing approach, routing state update messages may be transmitted: (i) when a subject node finds a new destination or any neighbors of the subject node report same, (ii) when a destination becomes unreachable by the subject node or any of its neighbors, (iii) when the subject node finds that the change in the cost of a path to at least one destination exceeds a threshold delta, (iv) when a path implied in any of the labeled routing trees of the subject node leads to a loop, and/or a new successor chosen to a given destination has an address larger than an address of the subject node and a reported distance from the new successor to a particular destination is larger than a reported distance from a previous successor to that particular destination. Another embodiment provides a routing update message that includes information regarding performance characteristics and addressing information for a link of a computer network and a node of the network at a tail end of the link. In some cases, the routing update may further include a time stamp assigned by a node at a head end of the link, a type of service vector, and addressing information for the node at a head end of the link. The performance characteristics preferably include link state parameters (e.g., link delay, link cost, available bandwidth, and/or reliability) of the link, while the type of service vector preferably specifies a type of service routing tree in which the link is being used by a node transmitting the routing update message. The addressing information of the link is preferably specified in the form of a local link identifier assigned to the link by the node at a head end of the link.